package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC764 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 太绕，实在不想再调了
     * @return:
     */
    class Solution {
        public int orderOfLargestPlusSign(int N, int[][] A) {
            int[][][] dp = new int[N][N][4];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < 4; k++) dp[i][j][k] = 1;
                }
            }
            for (int[] z : A) {
                for (int k = 0; k < 4; k++) dp[z[0]][z[1]][k] = 0;
            }
            // one-pass算左和上
            for (int i = 1; i < N; i++) {
                for (int j = 1; j < N; j++) {
                    if (dp[i][j][0] == 0) continue;
                    dp[i][j][0] = 1 + dp[i][j - 1][0];
                    dp[i][j][1] = 1 + dp[i - 1][j][1];
                }
            }
            // one-pass算右和下
            for (int i = N - 2; i >= 0; i--) {
                for (int j = N - 2; j >= 0; j--) {
                    if (dp[i][j][2] == 0) continue;
                    dp[i][j][2] = 1 + dp[i][j + 1][2];
                    dp[i][j][3] = 1 + dp[i + 1][j][3];
                }
            }
            int ans = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int k = min(dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3]);
                    ans = Math.max(ans, k);
                }
            }
            return ans;
        }

        int min(int a, int b, int c, int d) {
            return Math.min(Math.min(a, b), Math.min(c, d));
        }
    }

    class Solution_FAIL {
        public int orderOfLargestPlusSign(int N, int[][] mines) {
            if (N == 1) {
                return (mines.length > 0 && mines[0].length > 0) ? 0 : 1;
            }

            int dp[][] = new int[N][N];
            if (null != mines && mines.length > 0 && mines[0].length > 0) {
                for (int[] mine : mines) {
                    dp[mine[0]][mine[1]] = -1;
                }
            }

            int maxCross = 0;
            for (int i = 0; i < N; i++) {
                dp[0][i] = dp[0][i] == -1 ? dp[0][i] : 1;
                dp[N - 1][i] = dp[N - 1][i] == -1 ? dp[N - 1][i] : 1;
                dp[i][0] = dp[i][0] == -1 ? dp[i][0] : 1;
                dp[i][N - 1] = dp[i][N - 1] == -1 ? dp[i][N - 1] : 1;

                maxCross = Math.max(maxCross, dp[0][i]);
                maxCross = Math.max(maxCross, dp[N - 1][i]);
                maxCross = Math.max(maxCross, dp[i][0]);
                maxCross = Math.max(maxCross, dp[i][N - 1]);
            }

            for (int i = 1; i <= N / 2; i++) {
                for (int j = i; j <= N / 2; j++) {
                    dp[i][j] = dp[i][j] == -1 ? -1 : getCurrentPosCross(dp, i, j, 1, N);
                    dp[i][N - j - 1] = dp[i][N - j - 1] == -1 ? -1 : getCurrentPosCross(dp, i, N - j - 1, 2, N);
                    dp[N - 1 - i][j] = dp[N - 1 - i][j] == -1 ? -1 : getCurrentPosCross(dp, N - 1 - i, j, 3, N);
                    dp[N - 1 - i][N - i - j] = dp[N - 1 - i][N - i - j] == -1 ? -1 : getCurrentPosCross(dp, N - 1 - i, N - i - j, 4, N);

                    maxCross = Math.max(maxCross, dp[i][j]);
                    maxCross = Math.max(maxCross, dp[i][N - j - 1]);
                    maxCross = Math.max(maxCross, dp[N - 1 - i][j]);
                    maxCross = Math.max(maxCross, dp[N - 1 - i][N - i - j]);
                }
            }

            return maxCross;
        }

        public int getCurrentPosCross(int[][] dp, int i, int j, int part, int N) {
            if (1 == part) {
                int cross = Math.min(dp[i - 1][j], dp[i][j - 1]);
                if (cross < 0) return 0;
                if ((i + cross - 1 >= N) || (j + cross - 1 >= N) || (dp[i + cross - 1][j] == -1) || (dp[i][j + cross - 1] == -1))
                    return cross - 1;
                if ((i + cross >= N) || (j + cross >= N) || (dp[i + cross][j] == -1) || (dp[i][j + cross] == -1))
                    return cross;
                else return cross + 1;
            }

            if (2 == part) {
                int cross = Math.min(dp[i - 1][j], dp[i][j + 1]);
                if (cross < 0) return 0;
                if ((i + cross - 1 >= N) || (j - cross + 1 <= 0) || (dp[i + cross - 1][j] == -1) || (dp[i][j - cross + 1] == -1))
                    return cross - 1;
                if ((i + cross >= N) || (j - cross <= 0) || (dp[i + cross][j] == -1) || (dp[i][j - cross] == -1))
                    return cross;
                else return cross + 1;
            }

            if (3 == part) {
                int cross = Math.min(dp[i + 1][j], dp[i][j - 1]);
                if (cross < 0) return 0;
                if ((i - cross + 1 <= 0) || (j + cross - 1 >= N) || (dp[i - cross + 1][j] == -1) || (dp[i][j + cross - 1] == -1))
                    return cross - 1;
                if ((i - cross <= 0) || (j + cross >= N) || (dp[i - cross][j] == -1) || (dp[i][j + cross] == -1))
                    return cross;
                else return cross + 1;
            }

            if (4 == part) {
                int cross = Math.min(dp[i + 1][j], dp[i][j + 1]);
                if (cross < 0) return 0;
                if ((i - cross + 1 <= 0) || (j - cross + 1 <= 0) || (dp[i - cross + 1][j] == -1) || (dp[i][j - cross + 1] == -1))
                    return cross - 1;
                if ((i - cross <= 0) || (j - cross <= 0) || (dp[i - cross][j] == -1) || (dp[i][j - cross] == -1))
                    return cross;
                else return cross + 1;
            }

            return 0;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] arr = InputUtil.toDoubleIntegerArray("[[0,0],[0,1],[1,0]]");
        System.out.println(solution.orderOfLargestPlusSign(2, arr));
    }

    public static void main(String[] args) throws Exception {
        LC764 an = new LC764();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
